The present invention relates to the field of signal processing, and in particular, to an improved system and method for identifying which signal vector in a collection of signal vectors is nearest (in the sense of some norm) to a given input signal vector.
Many problems in engineering and the applied sciences reduce to the problem of distance minimization, i.e. the problem of identifying which vector in a particular collection of vectors is closest to a given input vector. For example, in the field of telecommunications, a transmitter may transmit a stream of symbols from a predefined set of symbols. Each of the predefined symbols may be associated with a corresponding bit pattern. A receiver may receive the stream of symbols corrupted with noise, and may perform a distance minimization to map each of the received symbols to one of the predefined symbols.
Another fundamental problem in the field of telecommunications is the so-called delay estimation problem. A transmitter may transmit a known template signal to a receiver. A receiving device may receive a delayed and noise-perturbed version of the known template signal. The receiving device may perform a distance minimization to estimate the time-delay between the received signal (i.e. the delayed noise-perturbed version of the template signal) and the template signal. Namely, the receiving device may generate an ensemble of time-delayed versions of the template signal, and may select the particular time-delayed version of the ensemble which is closest to the received signal in the sense of some vector norm. When the norm is the Euclidean norm, this distance minimization is equivalent to traditional autocorrelation.
In general, the distance minimization problem may be stated as follows. Given a collection X of vectors (e.g. signals, sequences, codes, symbols, etc.) and an input vector, identify the particular vector in the collection X which is closest to the input vector in the sense of some vector norm. In many situations, it is possible to assume that the input vector is within a distance r from exactly one of the vectors in the collection X, where distance r is less than or equal to xc2xd of the minimum distance between vectors in the collection X. This assumption will be referred to herein as the bounding assumption. An analysis of the noise mechanisms which perturb input vectors away from the collection X may give rise to an estimate for distance r.
Given a collection of N vectors P(0), P(1), P(2), . . . , P(Nxe2x88x921), and an input vector which obeys the bounding assumption with respect to the collection and a bounding radius r, one prior art method for identifying the closest vector in the collection to the input vector may be described as follows:
k=0;
MORE: compute S(k)=∥P(k)xe2x88x92g∥
if (S(k) less than r)
Output k as closest vector index;
Return;
else
k=k+1
goto MORE
endif
wherein ∥.∥ denotes a given vector norm. In other words, this prior art algorithm prescribes sequentially searching through the collection of vectors until the solution vector is identified. The solution vector is distinguished by having a distance from input vector g which is smaller than the bounding radius r. This sequential search algorithm identifies the solution vector in N/2 iterations on average, and at worst case in N iterations.
In many applications, the average convergence in N/2 iterations provided by the sequential search algorithm may be too slow, especially when N is large. Thus, there exists a need for a system and method which could more efficiently determine the signal vector from a collection of signal vectors which is closest to a given input vector.
Furthermore, the sequential search algorithm provides no mechanism for increasing the convergence rate when the bounding radius is small, i.e. when input vectors tightly cluster around vectors of the vector collection X. Thus, there exists a need for a system and method which could identify the solution vector (i.e. the vector with minimum distance to the input vector) with increased speed when the bounding radius r is small.
A signal analysis system and method according to the present invention may, at least in some embodiments, address the problems described above associated with determining the closest vector in a vector collection to a given input signal vector. The signal analysis system may comprise an input (e.g. a receiving device), a memory (e.g. one or more of RAM, ROM, non-volatile memory, etc.), and a processing unit. The memory may store a collection of vectors, and a table of mutual distances between pairs of the vectors in the collection. The memory may also store a software program for determining the closest vector in the vector collection to the input signal vector.
The input may be configured to receive an input signal from a communication medium (e.g. the Public Switched Telephone Network, an Ethernet bus, a PCI bus, the atmosphere, an optical fiber, a transducer, etc.). The input signal may comprise a sequence of samples, e.g., a sequence of samples of an analog signal.
The processing unit may be coupled to the memory, and may be configured to receive an input vector corresponding to the input signal and execute the software program for determining the closest vector. The processing unit may be further configured to execute the following methodology starting with index m=0 in order to determine the closest vector in the vector collection X(0) to the given input signal vector. The closest vector is referred to herein as the solution vector.
(1) select a vector P(km) in the vector collection X(m);
(2) analyze the table of mutual distances to determine a filtered subset X(m+1) of the vector collection X(m), wherein the vectors of the filtered subset X(m+1) have a distance to the selected vector P(km) which is greater than a first value FVm and smaller than a second value SVm, where the first value and the second value depend on index m;
(3) set m=m+1, i.e. increment index m;
(4) repeat (1), (2) and (3) zero or more times;
(5) identify a solution vector from the filtered collection, preferably after one or more iterations of (1), (2) and (3); and
(6) provide an output indication to a user in response to said identification of the solution vector.
Because of (3), the filtered subset X(m+1) becomes a new vector collection X(m) in a subsequent iteration of (1) and (2). The processing unit may repeat (1), (2) and (3) zero or more times until the selected vector P(km) has a distance from the input signal which is less than a bounding radius value.
The processing unit may be further configured to (c) compute a distance S(m) between the selected vector P(km) and the input vector, and (d) determine if the distance S(m) is smaller than the bounding radius value. The processing unit is configured to perform (c) and (d) after (1) and prior to (2). The processing unit may compute the first value FVm by subtracting the bounding radius value from the distance S(m), and compute the second value SVm by adding the bounding radius value to the distance S(m).
In the preferred embodiment, the memory stores a minimum distance data determination program. The processing unit may be configured to iteratively perform (1), (2), and (3) in response to execution of the minimum distance data determination program.
In a shift estimation or time-delay estimation application, the collection of vectors may represent shifted (e.g. delayed) versions of a known template signal, and input signal vector may represent a shifted and noise-perturbed version of the template signal, wherein the shift value (e.g. time-delay) is not known beforehand. The solution vector provides an estimate of the shift value. The output indication provided to the user may comprise an indication of the shift value or a data value computed in response to the shift value. For example, in a radar application, the shift value may be converted to an estimated range for a reflecting object (e.g. an aircraft), and the estimated range may be displayed on a display device (e.g. a screen, a head mounted display, a projection screen, etc.).
In a pattern recognition application, the collection of vectors may be feature pattern vectors representing various physical objects (or images), and the input signal vector may represent a sequence of features extracted from a given input object (or image), i.e. an initially unknown one of the physical objects (or images). The solution vector represents a selection of the one physical object (or image) that identifies the given input object from the set of physical objects. The output indication provided to the user may indicate the selected object (or image). For example, the output indication may comprise highlighting a visual representation of the selected object (or image) on a display screen.
In a telecommunications application, the collection of vectors represent codes (or symbols) which are assigned to corresponding bit patterns, and the input signal vector represents one of the codes perturbed by noise. In this case, the solution vector indicates which code the input signal vector xe2x80x9cbelongs toxe2x80x9d with highest likelihood. The bit pattern corresponding to the solution code may be sent to an output buffer. A stream of input signal vectors may be thus identified with their solution codes, and the resulting bit patterns may be accumulated into a digital output stream. The digital output stream may comprise a voice stream, a video stream, a stream of measurement and/or sensor data, etc. The digital output stream may be converted into an analog signal and present to the user in audible form through a speaker as in a telephony application (e.g. a cellular phone application, an Internet telephony application, etc.), in visual form through a display device (such as a monitor, a head-mounted display), etc.
In one application, the input signal comprises a localized subset of pixel values sampled from a particular locality in a xe2x80x9cpixilatedxe2x80x9d image (i.e. an image comprising a plurality of pixels). Furthermore, the collection of vectors comprise rotated versions of a representative subset of pixel values sampled from a template image. In this application, the solution vector indicates the orientation of the template image in the pixilated image.